#include <iostream>
#include <cstdio>
#include <string>
#include <filesystem>

using namespace std;
const int N = 1e6 + 5;
int f[N], n, T, ans[N];

void solve() {
    f[1] = f[2] = 1;
    for(int i = 3; i <= N; i++) {
        f[i] = f[i-1] % 9 + f[i-2] % 9;
        f[i] %= 9;
    }
    for(int i = 1; i <= N; i++) {
        ans[i] = (ans[i-1] + f[i]) % 9;
    }
}

int main() {
    // 创建sample目录
    filesystem::create_directory("sample");
    
    // 预处理答案
    solve();
    
    // 处理data目录下的所有测试数据
    for(int i = 1; i <= 20; i++) {
        string in_file = "data/fib" + to_string(i) + ".in";
        string out_file = "data/fib" + to_string(i) + ".out";
        
        freopen(in_file.c_str(), "r", stdin);
        freopen(out_file.c_str(), "w", stdout);
        
        cin >> T;
        while(T--) {
            scanf("%d", &n);
            printf("%d\n", ans[n]);
        }
        
        // 如果是第1、2、3组数据，复制到sample目录
        if(i <= 3) {
            string sample_in = "sample/fib" + to_string(i) + ".in";
            string sample_out = "sample/fib" + to_string(i) + ".ans";
            filesystem::copy_file(in_file, sample_in, filesystem::copy_options::overwrite_existing);
            filesystem::copy_file(out_file, sample_out, filesystem::copy_options::overwrite_existing);
        }
    }
    
    return 0;
} 